﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
using System.IO;
/*
 * 根据这个论文
Evaluating the state probabilities of M out of N sliding window detectors 
*/
namespace EvaluateMN2
{
    #region Hexad类
    /// <summary>
    /// 根据论文《 Evaluating the state probabilities of M out of N sliding window detectors 》实现Hexad类
    /// </summary>
    public class Hexad
    {
        //public UInt32 H { get; set; }       // 状态值. 默认全F为*
        public double P { get; set; }       // 该状态概率
        public UInt32 H_plus { get; set; }  // 收到正的值后的H+值
        public UInt32 H_minus { get; set; } // 收到负的值后的H-值
        public double P_plus { get; set; }  // 上一个状态（上一个状态满足收到正值后变为H）的概率
        public double P_minus { get; set; } // 上一个状态（上一个状态满足收到负值后变为H）的概率

        public Hexad(double p = 0, UInt32 hplus = 0, UInt32 hminus= 0, double pplus = 0, double pminus = 0)
        {
            //H = h;
            P = p;
            H_plus = hplus;
            H_minus = hminus;
            P_plus = pplus;
            P_minus = pminus;
        }

    }
    #endregion

    #region EvaluateMN
    /// <summary>
    /// 对m/n滑动窗的检测概率的评估的类
    /// </summary>
    public class EvaluateMN
    {
        //key:H
        public Dictionary<UInt32,Hexad> SetsOfMN = new Dictionary<UInt32, Hexad>();

        List<double> SetsOfP = new List<double>();  // 存储刚好在某个时刻检测到结果的概率
        double lstp = 0.0; // 上一个时刻概率
        // 检测概率输出文件
        StreamWriter psw = new StreamWriter(".\\presult.txt", false, Encoding.GetEncoding("gb2312"));
        // H集合输出
        StreamWriter deepsw = new StreamWriter(".\\deepsw.txt", false, Encoding.GetEncoding("gb2312"));
        public UInt32 M { get; set; }

        public UInt32 N { get; set; }
        public static LinkBinaryTree<int> btree = new LinkBinaryTree<int>(0); // 用来计算递归深度的
        public EvaluateMN(UInt32 m, UInt32 n)
        {
            M = m;
            N = n;
        }

        /// <summary>
        ///  自行实现的非递归的方式（遍历方法）给出所有H, 这些H满足包含不高于m-1个1。集合为非最小马尔科夫集合。
        ///  实现这个函数的缘由：AddHexad2S_Algorithm4()函数在n较大的情形下，容易出现递归溢出
        ///  注意：初始化时只用
        ///  AddHexad2S_Algorithm3()  或者
        ///  AddHexad2S_Algorithm5()  或者
        ///  AddHexad2S_no_recursion() 
        ///  两者之一
        /// </summary>
        public void AddHexad2S_no_recursion()
        {

            UInt32 maxv = UInt32.MaxValue >> (int)(32 - N + 1);
            SetsOfMN[0] = new Hexad(1, M == 1 ? UInt32.MaxValue : 1); // h.H=0
            
            for (UInt32 H = 1; H <= maxv; H++)
            {
                Hexad hexad = new Hexad(0);
   
                if (OneCount2(H, N - 1) > M - 1)
                {
                    continue;
                }
                else if (OneCount2(H, N - 1) == M - 1)
                {
                    hexad.H_plus = UInt32.MaxValue; // H包含m-1个1，则H_plus值为*态 （也成为A态，即吸收态）
                }
                else
                {
                    hexad.H_plus = ((H << 1) + 1) & (UInt32.MaxValue >> (int)(32 - N + 1));
                }

                hexad.H_minus = (H << 1) & (UInt32.MaxValue >> (int)(32 - N + 1));

                SetsOfMN[H] = hexad;
            }
            Hexad end = new Hexad(0, UInt32.MaxValue, UInt32.MaxValue, 0, 0);
            SetsOfMN[UInt32.MaxValue] =end; // 添加 * 状态
        }

        /// <summary>
        ///  初始化S集合，采用递归方式给出所有H. 本集合非最小马尔科夫集合
        ///  《 Evaluating the state probabilities of M out of N sliding window detectors 》 论文的Algorithm 3
        ///  注意：初始化时只用
        ///  AddHexad2S_Algorithm3()  或者
        ///  AddHexad2S_Algorithm5()  或者
        ///  AddHexad2S_no_recursion() 
        ///  两者之一
        /// </summary>
        public void AddHexad2S_Algorithm3()
        {
            try
            {
                Hexad hexad = new Hexad();

                AddHexad_Algorithm4(0, hexad, btree.Head);
                deepsw.WriteLine($"{M}/{N} : {btree.MaxDeepLevel}"); // 记录最大递归深度
                deepsw.Close();
                hexad.P = 1;
            }
            catch(Exception ex)
            {
                Console.WriteLine(ex.GetType() + ":"+ ex.Message);
            }
        }

        /// <summary>
        /// 由AddHexad2S_Algorithm3()函数调用，用递归方式生成所有的H. 非最小马尔科夫集合。 论文的Algorithm4
        /// </summary>
        /// <param name="hexad"></param>
        private void AddHexad_Algorithm4(UInt32 H, Hexad hexad, TreeNode<int> tnode = null, int leftOrRight = 0)
        {
            try
            {
                TreeNode<int> tnodeleft = null, tnoderight = null;

                switch (leftOrRight)
                {
                    case 0:
                        if (tnode != null)
                        {
                            tnodeleft = btree.InsertL(0, tnode);
                            tnoderight = btree.InsertR(0, tnode);
                        }
                        break;
                    case 1:
                        tnodeleft = tnoderight = btree.InsertL(0, tnode);
                        break;
                    case 2:
                        tnodeleft = tnoderight = btree.InsertR(0, tnode);
                        break;
                }

                SetsOfMN[H] = hexad;

                if (H == UInt32.MaxValue)
                {
                    hexad.H_plus = UInt32.MaxValue;
                    hexad.H_minus = UInt32.MaxValue;
                    return;
                }

                if (OneCount2(H, N - 1) == M - 1)
                {
                    hexad.H_plus = UInt32.MaxValue;
                }
                else
                {
                    hexad.H_plus = ((H << 1) + 1) & (UInt32.MaxValue >> (int)(32 - N + 1));
                }

                hexad.H_minus = (H << 1) & (UInt32.MaxValue >> (int)(32 - N + 1));

                bool find = SetsOfMN.Keys.Contains(hexad.H_plus);
                if (!find)
                {

                    btree.InsertL(0, tnode);
                    Hexad newHexad = new Hexad();
                    AddHexad_Algorithm4(hexad.H_plus, newHexad, tnodeleft, 1);
                }
                find = SetsOfMN.Keys.Contains(hexad.H_minus);
                if (!find)
                {
                    btree.InsertR(0, tnode);
                    Hexad newHexad = new Hexad();
                    AddHexad_Algorithm4(hexad.H_minus, newHexad, tnoderight, 2);

                }
            }
            catch(Exception ex)
            {
                Console.WriteLine(ex.GetType()+":"+ex.Message);
            }
        }


        /// <summary>
        ///  初始化S集合，采用递归方式给出所有H. 本集合为最小马尔科夫集合
        ///  《 Evaluating the state probabilities of M out of N sliding window detectors 》 论文的Algorithm 5
        ///  注意：初始化时只用
        ///  AddHexad2S_Algorithm3()  或者
        ///  AddHexad2S_Algorithm5()  或者
        ///  AddHexad2S_no_recursion() 
        ///  两者之一
        /// </summary>
        public void AddHexad2S_Algorithm5()
        {
            Hexad hexad = new Hexad();

            AddHexad_Algorithm6(0, hexad, btree.Head);
            deepsw.WriteLine($"{M}/{N} : {btree.MaxDeepLevel}");// 记录最大递归深度
            deepsw.Close();
            hexad.P = 1;
        }

        /// <summary>
        /// 由AddHexad2S_Algorithm5()函数调用，用递归方式生成所有的H. 为最小马尔科夫集合。 论文的Algorithm6
        /// </summary>
        /// <param name="hexad"></param>
        private void AddHexad_Algorithm6(UInt32 H, Hexad hexad, TreeNode<int> tnode = null, int leftOrRight = 0)
        {

            TreeNode<int> tnodeleft = null, tnoderight = null;

            switch (leftOrRight)
            {
                case 0:
                    if (tnode != null)
                    {
                        tnodeleft = btree.InsertL(0, tnode);
                        tnoderight = btree.InsertR(0, tnode);
                    }
                    break;
                case 1:
                    tnodeleft = tnoderight = btree.InsertL(0, tnode);
                    break;
                case 2:
                    tnodeleft = tnoderight = btree.InsertR(0, tnode);
                    break;
            }

            SetsOfMN[H] = hexad;

            if (H == UInt32.MaxValue)
            {
                hexad.H_plus = UInt32.MaxValue;
                hexad.H_minus = UInt32.MaxValue;
                return;
            }

            if (OneCount2(H, N - 1) == M - 1)
            {
                hexad.H_plus = UInt32.MaxValue;
            }
            else
            {
                UInt32 n_plus = ((H << 1) + 1) & (UInt32.MaxValue >> (int)(32 - N + 1)); ;

                hexad.H_plus = SmallestEquivalentHistory_Algorithm7(n_plus);
            }
            UInt32 n_minus = (H << 1) & (UInt32.MaxValue >> (int)(32 - N + 1));
            hexad.H_minus = SmallestEquivalentHistory_Algorithm7(n_minus);

            bool find = SetsOfMN.Keys.Contains(hexad.H_plus);
            if (!find)
            {
                Hexad newHexad = new Hexad();
                btree.InsertL(0, tnode); 
                AddHexad_Algorithm6(hexad.H_plus, newHexad, tnodeleft, 1);
            }
            find = SetsOfMN.Keys.Contains(hexad.H_minus);
            if (!find)
            {
                Hexad newHexad = new Hexad();
                btree.InsertR(0, tnode);
                AddHexad_Algorithm6(hexad.H_minus, newHexad, tnoderight, 2);

            }
            //Console.WriteLine("End");
        }

        /// <summary>
        /// 计算某个H=i状态的最小的等价状态。对应论文的 Algorithm 7
        /// </summary>
        /// <param name="i">表示H=i状态</param>
        /// <returns></returns>
        UInt32 SmallestEquivalentHistory_Algorithm7(UInt32 i)
        {
            UInt32 n, n_p;
            if (OneCount2(i, N-1) == M - 1)
            {
                return i;
            }
            else
            {
                n = ((i << 1) + 1) & (UInt32.MaxValue >> (int)(32 - N + 1)); ; // n = ((i x 2) mod 2^(N-1) + 1)
                n_p = SmallestEquivalentHistory_Algorithm7(n);
                if (n_p < i)
                    return n_p >> 1;
                else
                    return i;
            }

        }


        /// <summary>
        /// 计算某个数bit 1的个数
        /// </summary>
        /// <param name="v"></param>
        /// <param name="windowSize">表示在右侧的窗口大小</param>
        /// <returns></returns>
        static UInt32 OneCount2(UInt32 v, UInt32 windowSize)
        {
            v &= UInt32.MaxValue >> (int)(32 - windowSize);
            v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
            v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
            v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
            v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
            v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
            return v;
        }

        /// <summary>
        /// 运行检测概率计算
        /// </summary>
        /// <param name="prob">概率</param>
        /// <param name="maxtimes">最大运行次数</param>
        public void Run(double prob, int maxtimes)
        {
            int loopcnt = 0;
            int numb = SetsOfMN.Count();
            while(true)
            {
                foreach(var k in SetsOfMN.Keys)
                {
                    SetsOfMN[k].P_minus = SetsOfMN[k].P_plus = 0;
                }
                foreach (var k in SetsOfMN.Keys)
                {
                    SetsOfMN[SetsOfMN[k].H_plus].P_plus += SetsOfMN[k].P;
                    SetsOfMN[SetsOfMN[k].H_minus].P_minus += SetsOfMN[k].P;
                }
                foreach (var k in SetsOfMN.Keys)
                {
                    SetsOfMN[k].P = prob * SetsOfMN[k].P_plus + (1-prob) * SetsOfMN[k].P_minus;
                }
                Console.WriteLine($"{loopcnt}: {SetsOfMN[UInt32.MaxValue].P}");//{SetsOfMN[UInt32.MaxValue].P - lstp}
                psw.WriteLine($"{loopcnt}: {SetsOfMN[UInt32.MaxValue].P}");
                
                lstp = SetsOfMN[UInt32.MaxValue].P;
                loopcnt++;
                if(loopcnt >= maxtimes)
                {
                    psw.Close();
                    return;
                }
            }
        }

    }
    #endregion

    class Program
    {
        static void Main(string[] args)
        {
            var ev = new EvaluateMN(6, 20);
            ev.AddHexad2S_Algorithm3();
            //ev.AddHexad2S_Algorithm5();
            //ev.AddHexad2S_no_recursion();
            //ev.Run(0.9, 100);
            Console.WriteLine(ev.SetsOfMN.Count());
            Console.ReadLine();
        }
    }
}
